按公因数计算最大组件大小(Leetcode 952)

发表于 | 分类于 ， | | 本文总阅读数 次
| 字数统计: 1.4k | 阅读时长 ≈ 6
Leetcode 952

1

题目分析

   这是一个困难题，其实难度并没有这么大，就看小伙伴们有没有想到这个方法。

BFS

本题目是将有公因数的数字连起来，求最大的数字集合。我们思考一个小技巧，两个数是否有公因数，是不是要计算两者所有的因数呢？假如A和B有一个公因数C，C并不是一个质数，那么C可以分解成E x F，那么E和F也一定是A和B的公因数，因此我们只需要求出某个数的质数因子即可。

例如32和84是连通的。并不需要求32的所有因数，2、4、8、16、32，求84的所有因数2、3、4、6、7、12、14、21、28、42、84。而是只要将32拆分成2 x 2 x 2 x 2 x 2，即因数只有2，将84拆成2 x 2 x 3 x 7，即因数只有2、3、7。

一开始想到的是BFS算法，用numToFactor表示某个数的质因子，factorToNum表示某个质因子可以找到哪些数。并且用visitedFactor表示访问过的质因子，用visitedNum表示访问过的数。

此时可以从第一个数开始遍历，将质因子都加入到队列中，然后取出队列中的质因子，每个质因子都会从factorToNum中找到所有相关的数字，并将这些新找到的数字对应的质因子加入到队列中。

设有n个数字，数字的最大值为m，算法每个数字都只会访问一次，访问每个数字都需要$\sqrt(m)$的时间求出质因子，因此算法的*时间复杂度为$O(n\sqrt(m))$，要记录每个数的所有质因子、每个质因子相关的数字，因此空间复杂度也是$O(n*\sqrt(m))$**。

下面是Java语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
    private Map<Integer, List<Integer>> numToFactor = new HashMap<>();
    private Map<Integer, List<Integer>> factorToNum = new HashMap<>();
    private Set<Integer> visitedFactor = new HashSet<>();
    private Set<Integer> visitedNum = new HashSet<>();
    
    public int largestComponentSize(int[] nums) {
        for (int x : nums) {
            getFactor(x);
        }
        int max = 0;
        int current = 0;
        for (int x : nums) {
            if (!visitedNum.contains(x)) {
                current++;
                LinkedList<Integer> queue = new LinkedList<>();
                addFactor(x, queue);
                visitedNum.add(x);
                while (queue.size() > 0) {
                    int currentFactor = queue.pollFirst();
                    for (int num : factorToNum.getOrDefault(currentFactor, new ArrayList<>())) {
                        if (!visitedNum.contains(num)) {
                            current++;
                            addFactor(num, queue);
                            visitedNum.add(num);
                        }
                    }
                }
                max = Math.max(max, current);
                current = 0;
            }
        }
        return max;
    }

    private void getFactor(int x) {
        int cur = x;
        for (int i = 2; i * i <= cur; i++) {
            if (cur % i == 0) {
                cur /= i;
                putMap(x, i);
                while (cur % i == 0) {
                    cur /= i;
                }
            }
        }
        if (cur != 1) {
            putMap(x, cur);
        }
    }

    private void putMap(int x, int i) {
        List<Integer> factor = numToFactor.getOrDefault(x, new ArrayList<>());
        factor.add(i);
        numToFactor.put(x, factor);

        List<Integer> num = factorToNum.getOrDefault(i, new ArrayList<>());
        num.add(x);
        factorToNum.put(i, num);
    }

    private void addFactor(int x, LinkedList<Integer> queue) {
        for (int factor : numToFactor.getOrDefault(x, new ArrayList<>())) {
            if (!visitedFactor.contains(factor)) {
                queue.add(factor);
                visitedFactor.add(factor);
            }
        }
    }
}

并查集

BFS算法虽然能通过本题，但是构造了太多的Map和Set存储数据，而且逻辑也比较复杂，queue里面存放的是质因子，要根据质因子找到相关的数字，然后再根据数字找到质因子放入queue。queue里面存放数字也一样，要根据数字找到质因子，然后根据质因子找到相关数字放入queue。

对于这种连通问题，我们还可以尝试使用并查集去求解。分解出某个质因子就将该质因子与该数字加入到同一个集合中，思路非常清晰，代码也很简单优雅。

和BFS算法类似，也需要对于每一个数找到对应的质因子，而且在合并时找根的时候，需要$\alpha(n)$的时间复杂度，因此算法的**时间复杂度为$O(nlog(m)\alpha(n))$，值得注意的是，因为并查集初始化时，每个元素的根都是自己，因此所用空间是数组元素的最大值，空间复杂度为$O(m)$**。

因为$\alpha(n)$这个数比较小，而且避免了反复进队列、出队列、和操作Set和Map数据结构，因此耗时反而比BFS要短。

下面是Java语言的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
    public int largestComponentSize(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        UnionFind uf = new UnionFind(max + 1);
        for (int x : nums) {
            getFactor(x, uf);
        }
        int[] cnt = new int[max + 1];
        int res = 0;
        for (int x : nums) {
            res = Math.max(res, ++cnt[uf.getRoot(x)]);
        }
        return res;
    }

    private void getFactor(int x, UnionFind uf) {
        int cur = x;
        for (int i = 2; i * i <= cur; i++) {
            if (cur % i == 0) {
                uf.merge(x, i);
                cur /= i;
                while (cur % i == 0) {
                    cur /= i;
                }
            }
        }
        if (cur != 1) {
            uf.merge(x, cur);
        }
    }
}

class UnionFind {
    int[] rank;
    int[] root;

    UnionFind(int len) {
        root = new int[len];
        rank = new int[len];
        for (int i = 0; i < len; i++) {
            root[i] = i;
        }
    }

    int getRoot(int x) {
        if (root[x] == x) {
            return x;
        }
        return getRoot(root[x]);
    }

    void merge(int x, int y) {
        int rootX = getRoot(x);
        int rootY = getRoot(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

刷题总结

  因为练习比较少，一开始我也不喜欢使用并查集。而且并查集能解决的问题，一般DFS和BFS也都能解决。随着刷题的深入，发现一些题目用并查集确实比其他方法简单，小伙伴们如果遇到并查集，不要害怕，模板都是一样的，只是看你需要将什么数据加入到集合中罢了，要多多练习，勇敢面对。

-------------本文结束感谢您的阅读-------------
0%